﻿using System;
using Algoritmia.Utils;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.OrderStatistics
{
    public class QuickSelector<T> : ISelector<T>
    {
        private readonly Comparison<T> _comparison;

        public QuickSelector(Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
        }

        protected virtual int Partition(IList<T> a, int p, int r)
        {
            var pivot = a[r - 1];
            var i = p - 1;
            for (int j = p; j < r - 1; j++)
            {
                if (_comparison(a[j], pivot) <= 0)
                {
                    i++;
                    var aux = a[i];
                    a[i] = a[j];
                    a[j] = aux;
                }
            }
            var aux2 = a[i + 1];
            a[i + 1] = a[r - 1];
            a[r - 1] = aux2;
            return i + 1;
        }

        private T QuickSelect(IList<T> list, int k, int p, int r)
        {
            if (r - p == 1)
            {
                return list[p];
            }
            else
            {
                int q = Partition(list, p, r);
                if (k == q) return list[q];
                if (q > k) return QuickSelect(list, k, p, q);
                return QuickSelect(list, k, q + 1, r);
            }
        }

        #region Implementation of ISelector<T>

        public T Select(IList<T> list, int k)
        {
            if ( k <= 0 && k >= list.Count )
                throw new ArgumentOutOfRangeException("k");
            return QuickSelect(list, k, 0, list.Count);
        }

  

        #endregion
    }
}
